package leetcode_周赛._2024._01;

import java.util.HashSet;
import java.util.Set;

/**
 * 第 379 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2024/1/7 19:54
 */
public class _07 {

    /**
     * 捕获黑皇后需要的最少移动次数
     * 算法：分类讨论
     */
    public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        // 白车与黑皇在 同一行上. 如果白象在白车与黑皇中间, 需要移动白象
        if (a == e && (a != c || notInSide(b, d, f))) return 1;
        // 白车与黑皇在 同一列上. 如果白象在白车与黑皇中间, 需要移动白象
        if (b == f && (b != d || notInSide(a, c, e))) return 1;
        // 白像与黑皇在 同一斜线上. 如果白车在白象与黑皇中间, 需要移动白车
        // 处于 同一右斜线
        if (c + d == e + f && (a + b != c + d || notInSide(c, a, e))) return 1;
        // 处于 同一左斜线
        if (c - d == e - f && (a - b != c - d || notInSide(c, a, e))) return 1;
        return 2;
    }

    boolean notInSide(int a, int b, int c) {
        return !(Math.min(a, c) < b && b < Math.max(a, c));
    }


    /**
     * 移除后集合的最多元素数
     * 算法：分类讨论 + 贪心
     * 容斥原理：|A ∪ B| = |A| + |B| - |A ∩ B|
     */
    public int maximumSetSize(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Set<Integer> s1 = new HashSet<>(n), s2 = new HashSet<>(n);
        // 先排除自身重复的元素
        for (int num : nums1) s1.add(num);
        for (int num : nums2) s2.add(num);

        // s1 ∩ s2
        int common = 0;
        for (Integer x : s1) if (s2.contains(x)) ++common;

        int n1 = s1.size(), n2 = s2.size();
        int ans = s1.size() + s2.size() - common;

        // 还需要去掉的元素个数
        int m = n / 2, mn;
        if (n1 > m) {
            // 贪心：优先移除交集中的元素
            mn = Math.min(n1 - m, common);
            // d = n1 - m：n1 需要减去的个数
            // d - mn：优先减去交集中的元素
            // d - mn 后还大于 0, 需要减去除交集外的元素
            ans -= n1 - m - mn;
            common -= mn;
        }
        if (n2 > m) {
            mn = Math.min(n2 - m, common);
            ans -= n2 - m - mn;
        }
        return ans;
    }

}
